package com.my.algorithmlearning.leetcode;

/**
 * @ClassName Medium_221_MaximalSquare
 * @Description 优秀题解：https://leetcode.cn/problems/maximal-square/solutions/253739/221-zui-da-zheng-fang-xing-tu-jie-shi-pin-yan-shi-/
 * @Author wanghaiwei
 * @Date 2023/6/16 17:44
 */
public class Medium_221_MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        //dp[i][j]记录的是以i,j为右下角的正方形的最大边长
        int[][] dp = new int[matrix.length][matrix[0].length];
        int maxSide = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                } else if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        Medium_221_MaximalSquare maximalSquare = new Medium_221_MaximalSquare();

        char[][] input = new char[][]{{'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}};
        System.out.println(maximalSquare.maximalSquare(input));

        input = new char[][]{{'0', '1'}, {'1', '0'}};
        System.out.println(maximalSquare.maximalSquare(input));
    }
}
